/**
 * 1785. 构成特定和需要添加的最少元素
 * https://leetcode-cn.com/problems/minimum-elements-to-add-to-form-a-given-sum/
 */
public class Solutions_1785 {
    public static void main(String[] args) {
        int[] nums = {1, -1, 1};
        int limit = 3, goal = -4;  // output: 2

//        int[] nums = {1, -10, 9, 1};
//        int limit = 100, goal = 0;  // output: 1

        int result = minElements(nums, limit, goal);
        System.out.println(result);
    }

    /**
     * 解题思路：求商 + 余数
     * 1. 计算出 nums 中的元素和 sum
     * 2. 计算出元素和 sum 与 goal 差的绝对值 diff
     * 3. diff / limit，若不能整除，res 还需要加 1
     */
    public static int minElements(int[] nums, int limit, int goal) {
        // 累加和，需要用 long 类型
        long sum = 0;
        for (int num : nums) {
            sum += num;
        }
        long diff = Math.abs(sum - goal);
        long res = diff / limit;
        if (diff % limit > 0) {
            res += 1;
        }
        return (int) res;
    }
}
